#ifndef __GEEK_COMMANDER_HASH_H_INCLUDED_E7E58860_6E6B_4664_8A52_0F98AFB7437C__
#define __GEEK_COMMANDER_HASH_H_INCLUDED_E7E58860_6E6B_4664_8A52_0F98AFB7437C__

template<typename T>
struct geek_hashnode
{
    T *prev;
    T *next;
};

struct geek_hashtraits
{
    static const int hashtable_size = 1024;
};

template<typename T, typename H, geek_hashnode<T> T::*O, typename Tr = geek_hashtraits>
struct geek_hash
{
    typedef T item_t;
    typedef H hashfn_t;
    typedef Tr traits_t;

    item_t *hashtable[traits_t::hashtable_size];
    int item_count;

    static geek_hashnode<T> *get_hashnode(item_t *item)
    {
        return &(item->*O);
    }
};

template<typename H>
void geek_hash_create(H *hash)
{
    memset(hash,0,sizeof(H));
}

template<typename H>
void geek_hash_destroy(H *hash)
{
    memset(hash,0,sizeof(H));
}

template<typename H>
void geek_hash_insert(H *hash, typename H::item_t *item)
{
    int hashix = typename H::hashfn_t::calc(item) & (typename H::traits_t::hashtable_size-1);
    typename H::item_t **bucket = &hash->hashtable[hashix];

    if(*bucket == NULL)
    {
        H::get_hashnode(item)->next = NULL;
        H::get_hashnode(item)->prev = NULL;
    }
    else
    {
        H::get_hashnode(item)->next = *bucket;
        H::get_hashnode(item)->prev = NULL;
        H::get_hashnode(*bucket)->prev = item;
    }

    *bucket = item;
    hash->item_count += 1;
}

template<typename H>
void geek_hash_remove(H *hash, typename H::item_t *item)
{
    int hashix = typename H::hashfn_t::calc(item) & (typename H::traits_t::hashtable_size-1);
    typename H::item_t **bucket = &hash->hashtable[hashix];

    for(typename H::item_t *citem = *bucket; citem != NULL; citem = H::get_hashnode(citem)->next)
    {
        if(typename H::hashfn_t::compare(item,citem) == 0)
        {
            geek_hashnode<typename H::item_t> *node = H::get_hashnode(citem);

            if(node->next != NULL)
            {
                H::get_hashnode(node->next)->prev = node->prev;
            }

            if(node->prev != NULL)
            {
                H::get_hashnode(node->prev)->next = node->next;
            }

            if(*bucket == citem)
            {
                *bucket = node->next;
            }

            hash->item_count -= 1;
            break;
        }
    }
}

template<typename H>
typename H::item_t *geek_hash_find(H *hash, typename H::item_t *item)
{
    int hashix = typename H::hashfn_t::calc(item) & (typename H::traits_t::hashtable_size-1);
    typename H::item_t **bucket = &hash->hashtable[hashix];

    for(typename H::item_t *citem = *bucket; citem != NULL; citem = H::get_hashnode(citem)->next)
    {
        if(typename H::hashfn_t::compare(item,citem) == 0)
        {
            return citem;
        }
    }

    return NULL;
}

template<typename H>
void geek_hash_clear(H *hash)
{
    memset(hash,0,sizeof(H));
}

#endif // __GEEK_COMMANDER_HASH_H_INCLUDED_E7E58860_6E6B_4664_8A52_0F98AFB7437C__
